package com.yoshino.leetcode.improve40.Threetyforth;

import java.util.Arrays;
import java.util.List;

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int m = triangle.size();
        if (m == 1) {
            return triangle.get(0).get(0);
        }
        int[] dp = new int[m];
        // 下往上
        List<Integer> cur = triangle.get(m - 1);
        for (int i = 0; i < cur.size(); i++) {
            dp[i] = cur.get(i);
        }
        for (int i = m - 2; i >= 0; --i) {
            cur = triangle.get(i);
            for (int j = 0; j < cur.size(); j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + cur.get(j);
            }
        }
        return dp[0];
    }

    public boolean canPartition2(int[] nums) {
        // 0 1 背包问题
        if (nums.length < 2) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // 存储上一个状态的容量对应的价值
        int[] dp = new int[target + 1];
        for (int i = 0; i < nums.length; i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
            if (dp[target] == target) {
                return true;
            }
        }
        return false;
    }

    public boolean canPartition(int[] nums) {
        // 0 1 背包问题
        if (nums.length < 2) {
            return false;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        // 存储上一个状态的容量对应的价值
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < nums.length; i++) {
            // 放还是不放
            int num = nums[i];
            for (int j = target; j >= num; --j) {
                // 放入可不可以，得到相应的价值
                dp[j] |= dp[j - num];
            }
            if (dp[target]) {
                return true;
            }
        }
        return false;
    }

    public int findTargetSumWays(int[] nums, int target) {
        // 转换为 0 1 背包问题
        // 差 和 -> 求 sum - target 的差，只用考虑 和 问题，不用考虑 差
        if (nums.length == 0) {
            return 0;
        }
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        // 求 target -> 求 dif 和
        int dif = sum - target;
        if (dif < 0 || dif % 2 != 0) {
            // 将一个 + 变为 - ，相当于 减两次
            return 0;
        }
        // 求和为该数的可能情况
        dif /= 2;
        // 将可能转为 求可能得总会次数
        int[] dp = new int[dif + 1];
        // 辅助
        dp[0] = 1;
        for (int i = 0; i < nums.length; ++i) {
            // 放还是不放
            int num = nums[i];
            for (int j = dif; j >= num ; j--) {
                // 放入，和为 j 的不同放法
                dp[j] += dp[j - num];
            }
        }
        return dp[dif];
    }
}